package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 归并排序
 *
 * @author WangJX
 * @version 1.0
 * @date 2019/11/6 23:41
 */
public class MergetSort {
    public static void main(String[] args) {
//        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};


        //创建一个80000的随机数组
        int[] arr = new int[8000000];

        int[] tmp = new int[arr.length];


        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int)(Math.random() * 8000000);
        }

        //查看排序使用的时间
        Date d1 = new Date();
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println(sdf.format(d1));

        mergeSort(arr, 0, arr.length - 1, tmp);


        Date d2 = new Date();
        System.out.println(sdf.format(d2));



//        System.out.println(Arrays.toString(arr));
    }

    /**
     * 拆分、合并
     *
     * @param arr
     * @param left
     * @param right
     * @param tmp
     */
    public static void mergeSort(int[] arr, int left, int right, int[] tmp) {
        //递归拆分，知道拆到left=right时
        if (left < right) {
            int index = (left + right) / 2;
            //先把左边的全部拆完
            mergeSort(arr, left, index, tmp);
            //在拆解右边的
            mergeSort(arr, index + 1, right, tmp);
            //拆解完后对数据进行合并
            merge(arr, left, right, index, tmp);
        }

    }


    /**
     * 合并方法
     *
     * @param arr
     * @param left
     * @param right
     * @param mid
     * @param tmp
     */
    public static void merge(int[] arr, int left, int right, int mid, int[] tmp) {
        int l = left;   //左边的开始
        int r = mid + 1;  //右边数据的开始
        int index = 0;

        //因为左右两边数据是有序数组，所以分别取一个数据进行比较，小的先放入数组
        while (l <= mid && r <= right) {
            if (arr[l] <= arr[r]) {
                tmp[index] = arr[l];
                l += 1;
                index += 1;
            } else {
                tmp[index] = arr[r];
                r += 1;
                index += 1;
            }
        }

        //比较完后如果左边的数据还有剩余，则依次插入临时数组
        while (l <= mid) {
            tmp[index] = arr[l];
            l++;
            index++;
        }

        //比较完后如果右边的数据还有剩余，则依次插入临时数组
        while (r <= right) {
            tmp[index] = arr[r];
            r += 1;
            index += 1;
        }

        //依次把临时数组中的数据插入原数组中
        //因为在拆解的时候都拆成一个一个，所以第一次左边是0,右边是1，第二次左边是2开始，右边是3。
        // 当执行到第二轮第一次的时候，左边还是从0-1开始，右边是2-3开始...
        //第三轮第一次的时候左边还是0-3，右边变4-7...
        index = 0;
        int t = left;
        while (t <= right) {
            arr[t] = tmp[index];
            t += 1;
            index += 1;
        }

    }
}
